package com.example.leetdemo.finash;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution1417 {

    public String reformat(String s) {
        Stack<Character> abs = new Stack<>();
        Stack<Character> num = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) <= '9' && s.charAt(i) >= '0') {
                num.push(s.charAt(i));
            } else {
                abs.push(s.charAt(i));
            }
        }
        if (Math.abs(abs.size() - num.size()) > 1) {
            return "";
        }
        StringBuilder builder = new StringBuilder();
        if (abs.size() >= num.size()) {
            int length = num.size();
            for (int i = 0; i < length; i++) {
                builder.append(abs.pop());
                builder.append(num.pop());
            }
            if (abs.size() > 0) {
                builder.append(abs.pop());
            }
        } else {
            int length = abs.size();
            for (int i = 0; i < length; i++) {
                builder.append(num.pop());
                builder.append(abs.pop());
            }
            if (num.size() > 0) {
                builder.append(num.pop());
            }
        }
        return builder.toString();
    }

}
